package algorithm_diagram;

//二分查找条件：在一个有序的元素列表中查找一个数，花费logN时间
//创建一个有序元素的数组，最低位为0，最高位为数组长度-1，拿到数组中间位的数，判断与值相等即找到，大于值即最高位为中间位-1，
//小于值即最低位为中间位+1，重复循环此步骤直到最低位大于最高位或找到值
public class BinarySearch {

    public static void main(String[] args) {
        BinarySearch eSearch = new BinarySearch();
        int[] arr = {1, 3, 5, 7, 9,11,17,21,31,41,51,61,71,100};
        System.out.println(eSearch.binarySearch01(arr,51));
        System.out.println(eSearch.recursiveBinarySearch(arr,0,arr.length-1,51));
    }

    //循环二分查找
    private int binarySearch01(int[] list,int item){
        int low=0;
        int high=list.length-1;
        int mid;
        int guess;
        while(low<=high){
            mid=(low+high) >>> 1;
            guess=list[mid];
            if(guess==item){
                return mid;
            }else if(guess<item){
                low=mid+1;
            }else {
                high=mid-1;
            }
        }
        return -1;
    }

    //递归二分查找
    private int recursiveBinarySearch(int[] arr,int low,int high,int item){
        int mid=(low+high) >>> 1;
        if(low>high){
            return -1;
        }else{
            return arr[mid] == item ? mid : (arr[mid] > item ? recursiveBinarySearch(arr,low,mid-1,item) : recursiveBinarySearch(arr,mid+1,high,item));
        }

    }
}
